//  Copyright 2011 Charlie Garrett
//
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
//
//  Term.h
//

#ifndef TERM_H
#define TERM_H

#include <deque>
#include <set>
#include <string>

#include "logic.h"
#include "Value.h"

namespace logic {
    using namespace std;
    
    class TermVisitor;
    class CodeGenerator;
    class Constant;
    class Variable;
    class Register;

    // A Functor, combining name and argument count (arity) identifies the
    // heads of non-variable terms and also rules.  Constants have zero
    // argument (nullary) functors.
    struct Functor {
        string name;
        unsigned arity;
        
        Functor(string nm, int a) : name(nm), arity(a) {}
        
        string GetName() const {
            return name;
        }
        
        int GetArity() const {
            return arity;
        }
        
        bool Equals(const Functor &other) const;
        
        // Comparison operator for STL container classes.
        bool operator<(const Functor &other) const;
        
        string ToString() const;
        
        // Built-in Functors
        static Functor Undefined;
        static Functor ListCons;
    };
    
    // A Term is a piece of a program or query.  Concrete subclasses of Term are Constant,
    // Variable and Structure.
    class Term {
    public:
        Term() {}
        
        virtual bool IsConstant() const { return false; }
        virtual bool IsConstantNamed(const string &name) const { return false; }
        
        virtual bool IsVariable() const { return false; }

        virtual bool IsStructure() const { return false; }
        virtual bool IsStructureWithFunctor(const Functor &other) const { return false; }
        
        virtual const Functor *GetFunctor() const { return NULL; }
        virtual const Value *GetConstantValue() const { return NULL; }
        
        // Add any variables occurring in the term to the set.
        virtual void GetVariables(set<Variable*> *vars) = 0;
        
        // Accept visitors.
        virtual void Accept(TermVisitor *visitor) = 0;
        // Add children for visitors.
        virtual void AddChildren(TermVisitor *visitor, bool reversed = false) = 0;
        
        // Generate code to link a source level Variable and it's runtime register.
        virtual void LinkVariable(CodeGenerator *codegen) {}
        
        // Generate code for this Term.
        virtual void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                                 bool as_argument = false);
        virtual void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                               bool link_variables = false);
        
        virtual string ToString() const = 0;
    };
    
    // A Constant is a Term that represents a unique value, identified by
    // a name, or Functor with no arguments.
    class Constant : public Term {
    protected:
        Value value;
        
    public:
        Constant(string name) : Term(), value(name) {}
        
        Constant(double num) : Term(), value(num) {}
        
        bool IsConstant() const { return true; }
        bool IsConstantNamed(const string &name) const;

        // Add any variables occurring in the term to the set.
        void GetVariables(set<Variable*> *vars);
        
        const Value *GetConstantValue() const { return &value; }
        
        // Accept visitors.
        void Accept(TermVisitor *visitor);
        // Add children for visitors.
        void AddChildren(TermVisitor *visitor, bool reversed = false) {}
        
        // Generate code for this Term.
        void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                         bool as_argument = false);
        void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                       bool link_variables = false);
        
        string ToString() const;
    };
    
    class EmptyListConstant : public Constant {
    public:
        EmptyListConstant() : Constant("[]") {}
    };

    // A Variable is a Term that can be bound to another term.
    class Variable : public Term {
    private:
        string name;
        Term* value;
        
    public:
        Variable(string nm, Term *v = NULL) : Term(), name(nm), value(v) {}
        
        bool IsVariable() const { return true; }

        // Add any variables occurring in the term to the set.
        void GetVariables(set<Variable*> *vars);
        
        // Accept visitors.
        void Accept(TermVisitor *visitor);
        // Add children for visitors.
        void AddChildren(TermVisitor *visitor, bool reversed = false) {}

        // Generate code to link a source level Variable and it's runtime register.
        void LinkVariable(CodeGenerator *codegen);

        // Generate code for this Term.
        void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                         bool as_argument = false);
        void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                       bool link_variables = false);

        string ToString() const;
    };
    
    class Structure : public Term {
    protected:
        Functor functor;
        vector<Term*> subterms;
        
        void AddSubterms(deque<Term*> *worklist);
        Register DestReg(CodeGenerator *codegen, bool as_argument);
        void UnifySubterms(CodeGenerator *codegen);

        void GenerateSubtermQueryInstructions(CodeGenerator *codegen, bool link_variables);
        void SetSubterms(CodeGenerator *codegen, bool link_variables);
        
    public:
        Structure(string nm, vector<Term*> st) : Term(),
            functor(nm, (unsigned) st.size()), subterms(st) {}

        Structure(Functor f, vector<Term*> st) : Term(),
            functor(f), subterms(st) {
            assert(functor.GetArity() == subterms.size());
        }
        
        bool IsStructure() const { return true; }
        bool IsStructureWithFunctor(const Functor &other) const {
            return functor.Equals(other);
        }
        
        const Functor* GetFunctor() const {
            return &functor;
        }
        
        size_t NumSubterms() const { return subterms.size(); }
        Term *GetSubterm(size_t i) const { return subterms.at(i); }
        
        // Add any variables occurring in the term to the set.
        void GetVariables(set<Variable*> *vars);
        
        // Accept visitors.
        void Accept(TermVisitor *visitor);
        // Add children for visitors.
        void AddChildren(TermVisitor *visitor, bool reversed = false);
        
        // Generate code for this Term.
        void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                         bool as_argument = false);
        void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                       bool link_variables = false);
        
        string ToString() const;
    };
    
    // Builtin structure for list construction (i.e. [|]).
    class ListConsStructure : public Structure {
    public:
        ListConsStructure(vector<Term*> head_tail) :
            Structure(Functor::ListCons, head_tail) {}
        
        // Generate code for this Term.
        void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                         bool as_argument = false);
        void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                       bool link_variables = false);

        string ToString() const;
    };
    
    // Predicates are the top-level structure terms in rules and queries.
    class Predicate : public Structure {
    public:
        Predicate(string nm, vector<Term*> st) : Structure(nm, st) {}
        
        void AllocateArgRegisters(CodeGenerator *codegen);
        
        // Accept visitors.
        void Accept(TermVisitor *visitor);
        // Add children for visitors.
        void AddChildren(TermVisitor *visitor, bool reversed = false);
        
        void TranslateProgram(CodeGenerator *codegen);
        void TranslateQuery(CodeGenerator *codegen, bool link_variables = false);
        
        // Generate code for this Term.
        void GenerateProgramInstructions(CodeGenerator *codegen, deque<Term*> *worklist,
                                         bool as_argument = false);
        void GenerateQueryInstructions(CodeGenerator *codegen, bool as_argument = false,
                                       bool link_variables = false);
    };
    
    // TODO: Separate out Clause, Rule and Program, which are not terms.
    
    // Clauses consist of a head followed by 0 or more body atoms.
    class Clause {
    private:
        Predicate *head;
        vector<Predicate*> body;
        size_t clause_num;           // Order of clause in its parent rule.
        
    public:
        Clause(Predicate *hd, vector<Predicate*> bd) : head(hd), body(bd), clause_num(0) {}
        
        Predicate *GetHead() { return head; }
        size_t BodySize() { return body.size(); }
        Predicate *GetBodyAtom(unsigned i) { return body.at(i); }
        
        void SetClauseNum(size_t cn) { clause_num = cn; }
        
        void AllocatePermanentRegs(CodeGenerator *codegen);
        
        void Translate(CodeGenerator *codegen, size_t total_clauses);

        string ToString() const;
    };
    
    // A Rule is a list of clauses with the same predicate functor.
    class Rule {
    private:
        vector<Clause*> clauses;
        
    public:
        Rule(vector<Clause*> _clauses) : clauses(_clauses) {}
        
        size_t NumClauses() { return clauses.size(); }
        Clause *GetClause(unsigned i) { return clauses.at(i); }
        
        void AddClause(Clause *clause);

        void Translate(CodeGenerator *codegen);

        string ToString() const;
    };
    
    // A Program is a list of rules.
    class Program {
    private:
        vector<Rule*> rules;
        vector<Predicate*> queries;
        
    public:
        Program() : rules(), queries() {}
        Program(vector<Rule*> _rules) : rules(_rules) {}
        
        size_t NumRules() { return rules.size(); }
        Rule *GetRule(unsigned i) { return rules.at(i); }
        
        size_t NumQueries() { return queries.size(); }
        Predicate *GetQuery(unsigned i) { return queries.at(i); }
        
        // Allow programs to be extended one clause at a time.  The new clause is
        // appended to the list of clauses for the Rule corresponding to its Functor.
        void AddClause(Clause *clause);
        
        void AddQuery(Predicate *query);
        
        void Translate(CodeGenerator *codegen);
        void RunQuery(Predicate *query, bool trace = false);
        void RunQueries(bool trace = false);
        
        string ToString() const;
    };
}  // namespace logic

#endif  // TERM_H

